package com.itheima.d1_algorithm;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Arrays;

/**
 * 目标：掌握二分查找算法。
 *
 * 前提条件：数组中的数据必须是有序的
 * 核心思想：每次排除一半的数据，查询数据的性能明显提高极多！
 * 结论：二分查找正常的折半条件应该是开始位置left <= 结束位置right
 *
 * 注意：在数据量特别大的时候，基本查找这种从前往后挨个找的形式，性能是很差的！
 */

/**
 * 1、二分查找的实现步骤是什么样的?
 * 定义变量记录左边和右边位置。
 * 使用while循环控制二分查询（条件是左边位置<=右边位置）
 * 循环内部获取中间元素索引
 * 判断当前要找的元素如果大于中间元素，左边位置=中间索引+1
 * 判断当前要找的元素如果小于中间元素，右边位置=中间索引-1
 * 判断当前要找的元素如果等于中间元素，返回当前中间元素索引。
 */
public class Test3 {
    public static void main(String[] args) {
        // 1、准备好一个数组。
        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};

        System.out.println(binarySearch(arr, 150));

        //Java内部对二分查找的应用
        System.out.println(Arrays.binarySearch(arr, 81));


        System.out.println("============int类型的除法=============");

        int a1= 10;
        int b2 = 3;
        double c1=a1/b2;
        double c2=a1/b2;

        System.out.println("正常输出： "+c1);
        System.out.println("math的ceil方法: "+Math.ceil(c1));
        System.out.println("math的floor方法: "+Math.floor(c2));
        System.out.println(Math.ceil(3.2));
        System.out.println(Math.floor(3.2));

        System.out.println("==============转为double类型后和上面的int类型数据相除结果对比========");
        double a11 = 10;
        double b22 = 3;
        System.out.println("正常输出: "+a11/b22);
        System.out.println("math的ceil方法: "+ Math.ceil(a11/b22));
        System.out.println("math的floor方法： "+Math.floor(a11/b22));

        System.out.println("==========复习一下Bigdecimal方法========");

        BigDecimal s11 = BigDecimal.valueOf(10);
        BigDecimal s22 = BigDecimal.valueOf(3.0);

        BigDecimal s33 = s11.add(s22);
        System.out.println(s33);
        System.out.println(s11.divide(s22,2, RoundingMode.HALF_UP));


    }

    public static int binarySearch(int[] arr, int data){
        // 1、定义两个变量，一个站在左边位置，一个站在右边位置
        int left = 0;
        int right = arr.length - 1;

        // 2、定义一个循环控制折半。
        while (left <= right){
            // 3、每次折半，都算出中间位置处的索引
            int middle = (left + right) / 2;
            // 4、判断当前要找的元素值，与中间位置处的元素值的大小情况。
            if(data < arr[middle]){
                // 往左边找，截止位置（右边位置） = 中间位置 - 1
                right = middle - 1;
            }else if(data > arr[middle]){
                // 往右边找，起始位置（左边位置） = 中间位置 + 1
                left = middle + 1;
            }else {
                // 中间位置处的元素值，正好等于我们要找的元素值
                return middle;
            }
        }
        //最终左右位置重合了之后，还是没有找到元素，那就返回-1
        return -1; // -1特殊结果，就代表没有找到数据！数组中不存在该数据！
    }
}
